#include "Pass.h"
#include "ComSubExprEli.h"
#include <set>
#include <algorithm>

void ComSubExprEli::execute() {
    module->set_print_name();
     /*you need to finish this function*/
    for(auto fun: module->get_functions()){
        func_ = fun;
        in_block();
        //iteration();
        bool change = true; 
        for(auto bb: func_->get_basic_blocks()){
            IN_B[bb].clear();
            OUT_B[bb].clear();
        }
        while(change){
            change = false;
            for(auto bb: func_->get_basic_blocks()){
                    change = updatein(bb);
                    change = updateout(bb);
            }
        }
        between_block();
    }
}
bool ComSubExprEli::compare(Instruction *expr1,Instruction *expr2){ 
    bool result=false;
    if(expr1->get_instr_type()==expr2->get_instr_type()){
        ConstantInt * expr1_1 = dynamic_cast<ConstantInt *>(expr1->get_operand(0));
        ConstantInt * expr1_2 = dynamic_cast<ConstantInt *>(expr1->get_operand(1));
        ConstantInt * expr2_1 = dynamic_cast<ConstantInt *>(expr2->get_operand(0));
        ConstantInt * expr2_2 = dynamic_cast<ConstantInt *>(expr2->get_operand(1));
        if(((expr1_1&&expr1_1->get_value()==expr2_1->get_value())||
        (!expr1_1&&expr1->get_operand(0)==expr2->get_operand(0)))&&
        ((expr1_2&&expr1_2->get_value()==expr2_2->get_value())||
        (!expr1_2&&expr1->get_operand(1)==expr2->get_operand(1)))){
            result= true;
        }
        if(expr1->is_add()==true||expr1->is_mul()==true){
            if(((expr1_1&&expr1_1->get_value()==expr2_2->get_value())||
            (!expr1_1&&expr1->get_operand(0)==expr2->get_operand(1)))&&
            ((expr1_2&&expr1_2->get_value()==expr2_1->get_value())||
            (!expr1_2&&expr1->get_operand(1)==expr2->get_operand(0)))){
                result= true;
        }
        }
    }
    return result;
}
void ComSubExprEli::in_block(){ 
    std::set<Instruction *> delete_list;
    for(auto bb:func_->get_basic_blocks()){
        for(auto inst: bb->get_instructions()){
            bool repeat = false;
            if(is_valid_expr(inst)==0){
                continue;
            }
            for(auto expr: e_gen_B[bb]){
                if(compare(expr,inst)){
                    repeat = true;
                    for(auto use: inst->get_use_list()){
                        auto value = dynamic_cast<Value *>(expr);
                        Instruction * use_inst = dynamic_cast<Instruction *>(use.val_);
                        use_inst->set_operand(use.arg_no_, value);
                    }
                    Instruction * inst_dele=inst;
                    delete_list.insert(inst_dele);
                    break;
                }
            }
            if(!repeat){
                e_gen_B[bb].insert(inst);
            }
        }
        for(auto inst:delete_list){
            bb->delete_instr(inst);
         }
    }
}
bool ComSubExprEli::updatein(BasicBlock *bb){   
    std::set<Instruction *> in;
    std::map<BasicBlock *, Value *> overlap;
    std::list<BasicBlock *> precursor;
    precursor = bb->get_pre_basic_blocks();
    auto iter = precursor.begin();
    while(iter!=precursor.end()){
        auto pre = *iter;
        while(pre!=func_->get_entry_block()){
            if(pre==bb){
                precursor.erase(iter);
                break;
            }
            pre = pre->get_idom();
        }
        iter++;
    }
    bool f = false;
    if(precursor.empty()) return f;
    for(auto expr: OUT_B[precursor.front()]){
        overlap.clear();
        for(auto pre: precursor){
            for(auto exprp: OUT_B[pre]){
                if(compare(expr,exprp)){
                    overlap.insert({pre, dynamic_cast<Value *>(exprp)});
                    break;
                }
            }
        }
        if(overlap.size()==(unsigned int)(precursor.size())){
            in.insert(expr);
            bool q=false;
            auto iter = IN_B[bb].begin();
            while(iter != IN_B[bb].end()){
                q=compare(expr,*iter);
                iter++;
            }
            if(!q) f = true;
        }
   }
    IN_B[bb] = in;
    return f;
}
bool ComSubExprEli::updateout(BasicBlock *bb){  
    std::set<Instruction *> out;
    out = IN_B[bb];
    bool x = false;
    for(auto expr: e_gen_B[bb]){
        auto iter = IN_B[bb].begin();
        bool h=true;
        while(iter != IN_B[bb].end()){
            h=1-compare(expr,*iter);
            iter++;
        }
        if(h) out.insert(expr);
    }
    for(auto expr: out){
        auto iter = OUT_B[bb].begin();
        bool f;
        while( iter != OUT_B[bb].end()){
            f=1-compare(expr,*iter);
            iter++;
        }
        if(f) x = true;
    }
    OUT_B[bb] = out;
    return x;
}
void ComSubExprEli::between_block(){
    std::set<Instruction *> delete_list;
    for(auto bb: func_->get_basic_blocks()){
        for(auto inst: bb->get_instructions()){
            if(is_valid_expr(inst)==0){
                continue;
            }
            for(auto expr: IN_B[bb]){
                if(compare(inst,expr)){
                    for(auto use: inst->get_use_list()){
                        auto value = dynamic_cast<Value *>(expr);
                        Instruction * use_inst = dynamic_cast<Instruction *>(use.val_);
                        use_inst->set_operand(use.arg_no_, value);
                    }
                    Instruction * inst_dele=inst;
                    delete_list.insert(inst_dele);
                }
            }
        }
        for(auto inst:delete_list){
            bb->delete_instr(inst);
        }
    }
}
bool ComSubExprEli::is_valid_expr(Instruction *inst) {
    return !(inst->is_void()||inst->is_call()||inst->is_phi()||inst->is_alloca()||inst->is_load()||inst->is_cmp()||inst->is_zext());//TODO:CHECK VALID INST
}